# -*- coding: utf-8 -*-

"""剑指 Offer II 114. 外星文字典
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。

字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

示例 1：
输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"

示例 2：
输入：words = ["z","x"]
输出："zx"

示例 3：
输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。

提示：
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成"""

class Solution:
    """首先字符串列表中的字符已经按火星字典序排列，那么前后两个字符串比较可以得出两个字母的字典序。
    该列表遍历完之后，就形成一个字典序集合，也就是构建一个图。稀疏图，用邻接表构建，Dict{vertex: Set{vertex, ...}, ...}

    从图里任意那一个起点和终点的字母序列都能达到目的。
    问题的关键在于，所有字母序列都要合法，但凡有个不合法的序列，都返回空串。什么是不合法呢？也就是这个图中有环。所以本题的难点应该在图的环检测。

    看来还是曲解题意了，题目是还原出‘已知’的字母顺序，那么就是列表中给出的所有字母都得纳入一个序列。
    这就是经典的拓扑排序，中间加上环检测。"""
    def alienOrder(self, words: list) -> str:
        indegree = dict()
        for word in words:
            for letter in word:
                if letter not in indegree.keys():
                    indegree[letter] = 0

        graph = dict()
        size = len(words)
        i = 0
        while i < size-1:
            _pre, _next = words[i], words[i+1]
            min_length = min(len(_pre), len(_next))

            j = 0
            while j < min_length:
                _pl = _pre[j]
                _nl = _next[j]

                if _pl != _nl:
                    if _pl in graph.keys():
                        graph[_pl].add(_nl)
                    else:
                        graph[_pl] = set([_nl,])

                    break

                j += 1

            if j == min_length and len(_pre) > len(_next):
                return ''

            i += 1

        for _nextSet in graph.values():
            for letter in _nextSet:
                indegree[letter] += 1

        orders = ''
        while True:
            zero_in = list(filter((lambda letter: True if indegree[letter] == 0 else False), indegree.keys()))
            if not zero_in:
                break

            for letter in zero_in:
                orders += letter
                indegree.pop(letter)
                if letter in graph.keys():
                    for _next in graph[letter]:
                        indegree[_next] -= 1

        if len(indegree.keys()):
            return ''
        else:
            return orders


        print(indegree)
        print(graph)

if __name__ == '__main__':
    print(Solution().alienOrder(["wrt","wrf","er","ett","rftt"]))
    print(Solution().alienOrder(["z","x"]))
    print(Solution().alienOrder(["z","x","z"]))
